package br.com.rookgraph;

import java.util.Stack;

public class BranchReduce {
	
	// Mantem os dois estados
	private Graph original;
	private Graph tree;

	public BranchReduce(Graph original, Graph tree) {
		this.original = original;
		this.tree = tree;
	}

	public Graph excute() {
		Graph graphReduce = this.tree;
		
		boolean thereWasexchange = false;
		
		do{
			Aresta arestaCorte = findEdgeCut();
			
			graphReduce.removeEdge(arestaCorte.origin, arestaCorte.target);
						
			Aresta arestaSubstituta = findArestaLigacao(arestaCorte.target, new Aresta(-1, -1, -1));
			
			graphReduce.addEdge(arestaSubstituta.origin, arestaSubstituta.target, arestaSubstituta.value);
			
		}while(thereWasexchange);
		
		return graphReduce;
	}

	private Aresta findEdgeCut(){
		
		int[] branches = this.tree.getBranchs();
		
		int[] candidatas;
		int alfaCurrent = -1,  maiorAlfa = -1;
		Aresta arestaCorte = new Aresta(-1,-1,-1);
		for (int branch : branches) {
			
			candidatas = this.tree.getAdjacentes(branch);
			
			for (int candidata : candidatas) {
				
				alfaCurrent = this.tree.alfa(branch, candidata);

				if (alfaCurrent > maiorAlfa){
					maiorAlfa =  alfaCurrent;
					arestaCorte = new Aresta(branch, candidata, this.tree.getEdge(branch, candidata));
				}else{
					if (alfaCurrent == maiorAlfa){
						
						int sigCandidato = this.tree.sigma(branch, candidata);
						int sigArestaCorte = this.tree.sigma(arestaCorte.origin, arestaCorte.target);
						
						arestaCorte = sigCandidato < sigArestaCorte ? new Aresta(branch, candidata, this.tree.getEdge(branch, candidata)) : arestaCorte;
						
					}
				}
				
			}
			
		}
		return arestaCorte;
	}



	private Aresta findArestaLigacao(int rootSeg, Aresta aresta ) {
		
		int[] candidatas = this.original.getAdjacentes(rootSeg);
		int alfaMaior = this.original.alfa(aresta.origin, aresta.target); 
		
		Aresta arestaLigacao = aresta;
		for (int vAdj : candidatas) {

			if(!this.tree.hasEdge(rootSeg, vAdj)){
				int alfaAdj = this.original.alfa(rootSeg, vAdj);
		
				if(alfaAdj > alfaMaior){
					
				}else if(alfaAdj == alfaMaior){
						
						int sigmaAnt = this.original.sigma(aresta.origin, aresta.target);
						int sigmaAdj = this.original.sigma(rootSeg, vAdj);
						
						if( sigmaAdj > sigmaAnt){
							arestaLigacao = new Aresta(rootSeg, vAdj, this.original.getEdge(rootSeg, vAdj));
						}
				}
				
			}else{
				arestaLigacao = findArestaLigacao(vAdj, arestaLigacao);
			}	
			
		}		
		return arestaLigacao;
	}
	
	protected static class Aresta{
		
		int value;
		int origin;
		int target;
		
		public Aresta(int origin, int target, int value) {
			this.target = target;
			this.origin = origin; 
			this.value =  value;
		}
		
	}

}
